package com.xinxin.leetcode.problem475;

import java.util.Arrays;

/**
 * @author ShiXinXin
 * @date 2020-01-04 20:40
 */
public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int radius = 0;
        int k = 0;
        for (int i = 0; i < houses.length; i++) {
            int r = Math.abs(heaters[k] - houses[i]);
            for (int j = k + 1; j < heaters.length; j++) {
                if (Math.abs(heaters[j] - houses[i]) > r) {
                    break;
                }
                k = j;
                r = Math.abs(heaters[k] - houses[i]);
            }
            radius = Math.max(radius, r);
        }
        return radius;
    }

    public static void main(String[] args) {
        int[] houses = {282475249, 622650073, 984943658, 144108930, 470211272, 101027544, 457850878, 458777923};
        int[] heaters = {823564440, 115438165, 784484492, 74243042, 114807987, 137522503, 441282327, 16531729, 823378840, 143542612};
        System.out.println(new Solution().findRadius(houses, heaters));
    }
}
